import collections
import copy
from typing import List


class Solution:
    def containVirus(self, grid: List[List[int]]) -> int:
        ROW = len(grid)
        COL = len(grid[0])

        res = 0
        wall_built = [[False] * COL for _ in range(ROW)] #被建墙隔离的节点标志

        def neighbor(r, c):
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < ROW and 0 <= nc < COL:
                    yield nr, nc

        def BFS(r, c, vis):
            #BFS输入的节点确保是 病毒节点，且是没有被隔离的节点
            # 返回 1。威胁感染区域数量（即墙的数量）， 2。需要建墙的坐标
            # vis是单次在全局搜索连通域使用的标志

            wall_num = 0
            wall = []

            queue = collections.deque()
            queue.append((r, c))
            vis[r][c] = True

            while queue:
                r, c = queue.popleft()

                #need_wall = False  # 旁边有未感染区域才需要建墙
                #一个连通域如果建墙 就完全隔离 也就是该连通域的病毒就失效了

                for nr, nc in neighbor(r, c):
                    if grid[nr][nc] == 1 and vis[nr][nc] == False :# and wall_built[nr][nc] == False:
                        # 当前时刻下连通的感染区域 遍历. 对于被建墙隔离的节点就不算连通的
                        queue.append((nr, nc))
                        vis[nr][nc] = True

                    if grid[nr][nc] == 0 and wall_built[r][c] == False:
                        wall_num += 1

                wall.append((r, c))

            return (wall_num, wall)

        while True:
            #####
            # 单次循环
            vis = [[False] * COL for _ in range(ROW)]
            cur_block = []
            for r, row in enumerate(grid):
                for c, n in enumerate(row):
                    if n == 1 and vis[r][c] == False and wall_built[r][c] == False:
                        cur_block.append( BFS(r, c, vis) )

            if len(cur_block) == 0:  # 根本没有感染区
                break

            print([(n, len(walls)) for n, walls in cur_block])
            wall_num, walls = max(cur_block, key=lambda x: len(x[1]) )
            #############
            #我吐了 这里的判断条件写错了 是区域最大 不是建墙最多
            res += wall_num
            for wr, wc in walls:
                wall_built[wr][wc] = True

            # 感染区扩散
            spread = []
            for r, row in enumerate(grid):
                for c, n in enumerate(row):
                    if grid[r][c] == 1 and wall_built[r][c] == False:
                        for nr, nc in neighbor(r, c):
                            if grid[nr][nc] == 0:
                                spread.append((nr, nc))

            if len(spread) == 0: break

            for sr, sc in spread:
                grid[sr][sc] = 1

        return res


input_data = [[0,1,0,1,1,1,1,1,1,0],[0,0,0,1,0,0,0,0,0,0],[0,0,1,1,1,0,0,0,1,0],[0,0,0,1,1,0,0,1,1,0],[0,1,0,0,1,0,1,1,0,1],[0,0,0,1,0,1,0,1,1,1],[0,1,0,0,1,0,0,1,1,0],[0,1,0,1,0,0,0,1,1,0],[0,1,1,0,0,1,1,0,0,1],[1,0,1,1,0,1,0,1,0,1]]
print(Solution().containVirus(input_data))